package 小米笔试题;
import java.util.Scanner;
// https://blog.csdn.net/GXSeveryday/article/details/109091196
public class 小米9月2日笔试题密码学0902 {
/*

小汪作为一个有数学天分的程序猿，设计了一套密码生成器来搞定自己的密码问题。
密码生成器由N个槽位组成，槽位的下标为0~N-1，每个槽位存储一个数。起初每个槽位都是0。
密码生成器会进行M轮计算，每轮计算，小汪会输入两个数L,R(L<=R),密码生成器会将这两个数作为下标，将两个下标之间（包含）的所有槽位赋值为i（i为当前的轮次，i∈[1,M]）。
M轮计算完成后，密码生成器会根据槽位的最终值生成一条密码，密码的生成规则为： （0a[0] + 1a[1] + 2*a[2] + …

(N-1)*a[N-1]) mod 100000009 其中a[i]表示第i个槽位的最终值。 请帮助小汪把他的密码生成器实现为代码。
————————————————
版权声明：本文为CSDN博主「北顾丶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/GXSeveryday/article/details/109091196
 */
/*

输入描述:
第一行为两个整数N,M,表示槽位个数和计算轮数。
接下来M行，每行两个整数Li,Ri，表示第i轮计算的输入。
1
2
3
输出描述:
输出一行，一个整数A,表示小汪的开机密码。
1
2
示例1
输入
5 3
2 3
1 2
1 1
1
2
3
4
5
6
输出
10
 */


        public static void main(String[] args) {
            /**
             * int[n] int l int r int m
             * 1.读入n和m
             * 2.创建密码数组，初始值为0，长度为n
             * 3.建立循环，循环次数为m，进行m轮计算操作
             * 4.计算完成后，生成最终密码
             *
             * */
            //读入n和m
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            //创建密码数组，初始值为0，长度为n
            int[] password = new int[n];
            //建立循环，循环次数为m，进行m轮计算操作
            for (int i = 1; i <= m; i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                for(int j = l;j<= r;j++){
                    password[j]=i;
                }
            }
            long result = 0;
            for (int i = 0; i < password.length; i++) {
                result += (long)(i * password[i]);
            }
            result = result % 100000009L;
            //计算完成后，生成最终密码
            System.out.println(result);
        }
    }


